package org.example;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

public class Test1 {
    //leetcode 101 对称二叉树 https://leetcode.cn/problems/symmetric-tree/description/
    /**
     * 方法一：递归法
     * @param root
     * @return
     */
    public boolean isSymmetric1(TreeNode root) {
        return compare(root.left,root.right);
    }

    public boolean compare(TreeNode left,TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null && right != null) return false;
        if (left != null && right == null) return false;
        boolean leftRet = compare(left.left,right.right);
        if (!leftRet) return false;
        boolean rightRet = compare(left.right,right.left);
        if (!rightRet) return false;
        return left.val == right.val;
    }

    /**
     * 方法二：迭代法
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root.left);
        deque.add(root.right);
        while (!deque.isEmpty()) {
            TreeNode leftNode = deque.poll();
            TreeNode rightNode = deque.poll();
            if (leftNode == null && rightNode == null) continue;
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) return false;
            deque.add(leftNode.left);
            deque.add(rightNode.right);
            deque.add(leftNode.right);
            deque.add(rightNode.left);
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(2);
        TreeNode d = new TreeNode(3);
        TreeNode e = new TreeNode(3);
        TreeNode f = new TreeNode(4);
        TreeNode g = new TreeNode(4);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = f;
        c.left = g;
        c.right = e;
        Test1 test1 = new Test1();
        test1.isSymmetric(a);
        System.out.println(333);
    }
}
